#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int n = 20;
int arr[n];
using ll = long long;
//映射数组
const char ch[] = {'0','1', '2', '3', '4','5','6','7','8','9','A','B','C','D','E','F' };
void Solve()
{
    int N, M;//N为输入的数字的进制数，M为要转化为的目标进制数
    //先将N进制数转化为十进制数
    cin >> N >> M;
    string s;
    cin >> s;
    int len = s.length();
    s = "#" + s; // 方便遍历
    for (int i = 1; i <= len; i++)
    { 
        if (s[i] >= '0' && s[i] <= '9')
            arr[i] = s[i] - '0';
        else
            arr[i] = s[i] - 'A' + 10;
    }
    ll x = 0;
    //转化为十进制
    for (int i = 1; i <= len; i++)
    {
        x = x * N + arr[i];
    }
    //转化为M进制
    string ans;
    while (x)
    {
        ans += ch[x % M];
        x /= M;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

int main()
{
    int T;
    cin >> T;//处理的次数
    for (int i = 0; i < T; i++)
        Solve();
    return 0;
}
